package com.sort;

import java.util.Arrays;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: QuickSort
 * @description: 快速排序
 * @date 2021/2/710:37
 * @since V1.0
 */
public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {1,6,10,7,10,4,3,16,9,-1,900,23,4561,567};
        int[] arr = new int[8000000];
        for (int i=0;i<arr.length;i++){
            arr[i] = (int) (Math.random()*80000000);
        }
        long l = System.currentTimeMillis();
        quickSort(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));
        long l1 = System.currentTimeMillis();
        System.out.println((l1-l));
    }

    public static void quickSort(int[] arr,int lo,int ro){
        int left = lo;
        int right = ro;
        int pivot = arr[(left+right)/2];
        //相当于左右双指针遍历完这个序列
        while (left<right){
            while (arr[left]<pivot){
                left++;
            }
            while (arr[right]>pivot){
                right--;
            }
            if (left>=right){
                break;
            }
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            //避免该交换的元素刚好和pivot一样大小，不然就死循环了
            if (arr[left] == pivot){
                right--;
            }
            if (arr[right] == pivot){
                left++;
            }
        }
        //递归左边
        if (lo<left){
            quickSort(arr, lo, left-1);
        }
        //递归右边
        if (ro>right){
            quickSort(arr, right+1, ro);
        }
    }

}
